Content Addressable Memory (CAM) devices have been developed as an alternative to traditional memory devices such as well known DRAM and SRAM devices. CAM allows cells to be referenced by their contents, so it has found use in lookup table implementations such as cache memory subsystems and is now rapidly finding use in networking systems. A valuable feature of a CAM is its ability to perform a search and compare of multiple locations as a single operation, in which search data is compared with data stored within the CAM. Typically search data is loaded onto search lines and compared with stored words in the CAM. During a search-and-compare operation, a match or mismatch signal associated with each stored word is generated on a matchline, indicating whether the search word matches a stored word or not. The physical address of stored words that match the search data is then provided to the system for subsequent use. Examples of CAM architectures and circuits that illustrate the operation of CAM's are disclosed in commonly owned U.S. Pat. Nos. 6,320,777, 6,442,090, 6,307,798, 6,552,596, and 6,504,775.
CAM's are typically integrated within a system to provide content based search capability, where one or more CAM devices of the system define a search table having a number of entries equal to the sum of the capacities of each CAM device. CAM devices are available in a variety of densities, hence the desired total search table size of the system will determine the number of CAM devices to cascade together.
It is commonly desired to execute the same search repeatedly upon the CAM device in a networked system application. This involves setting up, or generating a data structure called a context comprising an instruction and search data each time a search operation is to be executed, which requires several cycles to setup. Accordingly, cycles are wasted if the same search operation is to be executed repeatedly. Thus to increase search efficiency, CAM contexts are used to store preset search instructions and search data, which can be executed with a single command. Each CAM context includes instruction bits, status bits and data bits sufficient to execute an operation on the CAM. Contexts can further include other control and configuration bits, all of which are stored in registers.
FIG. 1 shows a general CAM search sub-system that uses CAM contexts. The sub-system 10 of FIG. 1 includes a CAM interface 12 coupled to a pair of network processing units (NPU) 14, a single CAM 16 and an SRAM 18. CAM interface 12 has two network processor interface ports for communicating with NPU's 14, but can have more than two network processor interface ports for communicating with additional NPU's 14. SRAM 18 includes additional data associated with the data entries in CAM 16. Those of skill in the art will understand that CAM 16 and SRAM 18 can include a single device or a number of cascaded devices respectively. CAM interface 12 includes a predetermined number of sets of registers associated with each network processor interface port for access by the corresponding NPU 14. In particular, CAM interface 12 includes a predetermined number of context registers that are set up, or written, according to instructions provided by NPU 14. In addition to context registers, CAM interface 12 includes output registers for storing the results of the search executed by CAM 16 and any associated data stored in SRAM 18, and a context pipeline for issuing the contexts to be executed. While FIG. 1 illustrates separate CAM interface 12 and CAM 16 blocks, both are typically implemented as separate integrated circuits. However, those of skill in the art will realize that both can be combined within a single device or a multi-chip module.
In operation, NPU 14 first sets up its associated predefined contexts that will be stored in the context registers of CAM interface 12. To execute a search operation, NPU 14 issues a command to execute one or more specific contexts. The specified context or contexts are fed to the context pipeline, and are sequentially sent to CAM 16 for execution. The results of the search by CAM 16 are returned to CAM interface 12, and are stored in the output registers with its associated data from SRAM 18. NPU 14 can then issue a command to CAM interface 12 to provide the search results stored in the output registers. Each context in CAM interface 12 is stored in an order known to the user such that a single command can be issued by NPU 14 to execute the particular search defined by that context.
FIG. 2 is a graphical illustration of a context for CAM 12 that can be stored in CAM interface 12. Context 20 includes an instruction field 22, a status field 24, and a data field 26. Instruction field 22 can include a number of bits to represent any one of the predefined CAM instructions. Status field 24 stores a status key associated with each word stored in the CAM array, and can include status, control and configuration bits. Accordingly, data field 26 stores a data key that preferably includes the same number of bits as a single word in the CAM array.
Valuable NPU cycles are required for setting up each context 20 of FIG. 2 in CAM interface 12. In the present example, it is assumed that the instruction field 22 of context 20 is 16 bits wide and the status field 24 is 16 bits wide. It is further assumed that the data field 26 is 288 bits wide, and the interface to NPU 14 is a 16 bit wide LA-1 interface data port. Those of skill in the art will understand that the fields can be configured with any desired width, and that additional user configurable fields can be added if desired. Therefore one NPU clock cycle is required for loading the instruction field 22, one cycle is required for loading the status field 24, and 18 cycles (at a single data rate) are required for loading the data field 26. Hence a total of 20 cycles are required for setting up the context.
A type of repeated search operation is a burst search operation utilizing multiple contexts. For example, each context of the burst search operation uses the same data key in its data field, but uses different status keys. A known method of issuing a burst search operation with the same data key and different status keys is to fill a predetermined number of contexts with the same data key and instruction, but with a different status key data in each context. An example illustrating a set of contexts for such a burst search operation is shown in FIG. 3.
In FIG. 3, a context setup for a burst-of-4 search operation is shown using context 20 of FIG. 2 with the search sub-system of FIG. 1. It is assumed that the instruction field 22 of context 20 is 16 bits wide, the status field 24 is 16 bits wide, the data field 26 is 288 bits wide, and the interface to NPU 14 is a 16 bit wide LA-1 interface data port. For the purposes of illustrating the burst-of-4 search operation, only the three status bits of the status field shown in FIG. 3. Four contexts, 40, 42, 44 and 46 are successively setup with the same search instruction and data key, but with different status keys. Context 40, being the first context, is setup during cycles 0-19, with contexts 42, 44 and 46 each requiring 20 cycles for setup. A total of 80 cycles is thus required by NPU 14 for setting up the burst-of-4 search operation. Unfortunately, since the data keys of each context are identical to each other, the cycles required to set them up are considered wasted. The cycles required for setting up the contexts cannot be used for other operations by the NPU 14, hence reducing performance of search sub-system 10.
It is, therefore, desirable to provide a method for reducing the number of cycles required for setting up contexts.